
/******************************************************************
; Module:  Heap
;
; description:
;   This module implements a standard "heap" data structure.  The
;   heap has a maximum size, specified at heap creation time.
;
;   The heap "tree" is implemented as an array, with the typical
;   binary tree flattening technique:  given array entry i, its
;   two child nodes in the tree are at array entries 2i and 2i+1.
;   This indexing scheme preclues the use of array index 0 as a valid
;   entry in the heap.
;
;   The heap is designed to have the smallest elements at the top of
;   the heap.  Consequently, comaparing the top element with any other
;   element in the heap should return a non-positive value.  All
;   comparisons are done through a user-supplied compare routine
;   (semantics of strcmp for strinds or "key1 - key2" for integers).
;
;   The heap can be used to have the largest value at the top of the
;   heap by negating the sign of the comparison before returning it
;   to the heap module.
;
; history:
;   94.10.31 / M. McAllister / Created
;   94.11.01 / M. McAllister / HEAP_Allocate, HEAP_PeekNamed, HEAP_PopNamed
;                              HEAP_Add, HEAP_Audit
*******************************************************************/

#include "stdio.h"
#include "stdlib.h"
#include "string.h"

#include "globals.h"
#include "heapdefs.h"
#include "heap.h"

/******************************************************************
;  Forward declaration of local routines. 
*******************************************************************/

static void  SwapHeapItems (HEAP_Heap heapPtr, UInt16 first, UInt16 second);
static void  ClearHeapItem (HEAP_Heap heapPtr, UInt16 entry);
static UInt16 TrickleUp(HEAP_Heap heapPtr, UInt16 trickleStart);
static void  TrickleDown(HEAP_Heap heapPtr, UInt16 startPoint);

/******************************************************************
; routine:  HEAP_Allocate
;
; description:
;   Create a heap from system memory.  The heap size is configurable
;   at allocation time.
;
; in:
;   size : UInt16  -- the maximum number of elements that the heap
;                     must be able to handle (must be >= 0)
;   cmpRtn: SInt16 (*)(Ptr, Ptr) -- the comparison routine for two keys
;                  in the heap.  Returns positive if key1 > key2, 
;                  0 if key1 == key2, and negative if key1 < key2.
;                  (designed to match strcmp)
;   name : Char * -- an identification name for the heap; only used for
;                    debugging purposes.
;
; out:
;   returns : HEAP_Heap -- an identifier for the heap; this is the "heap"
;                       value that must be passed to all subsequent
;                       calls of heap routines.
;
; history:
;   94.10.31 / M. McAllister / Created
;   94.11.01 / M. McAllister / Enforce non-negative size constraint.
*******************************************************************/
HEAP_Heap 
HEAP_Allocate(UInt16 size, SInt16 (*cmpRtn)(Ptr, Ptr), Char *namePtr)
{
  HEAP_Heap heapPtr = HEAP_NullHeap;
  UInt16    i;
  UInt16    inNameSize;

  /*  A comparison routine must always be provided. */

  if (cmpRtn != NULL) {
    /* Allocate the heap construct. */

	heapPtr = (HEAP_Heap) malloc (sizeof(HEAP_HeapInfo));
	if (heapPtr != NULL) {

      /* Get the various arrays that are needed. */

	  heapPtr->refList = (HEAP_HeapId *)malloc(sizeof(HEAP_HeapId)*(size + 1));
	  heapPtr->dataList = (Ptr *)calloc(size + 1, sizeof(Ptr));
	  heapPtr->idList = (HEAP_HeapId *)calloc(size + 1, sizeof(HEAP_HeapId));

	  if ((heapPtr->refList == NULL) || 
		  (heapPtr->dataList == NULL) ||
		  (heapPtr->idList == NULL)) {

        /* Not enough space to build the array.  Give up. */

		free (heapPtr->refList);
		free (heapPtr->dataList);
		free (heapPtr->idList);
		free (heapPtr);
		heapPtr = NULL;
	  } else {

		/* Fill in the heap fields with the data provided and other
           initialization values. */

        if (namePtr != NULL) {
          inNameSize = strlen(namePtr);
		  strncpy(heapPtr->name, namePtr, Min(_HEAP_MaxNameSize-1, inNameSize));
        }
        heapPtr->headGuard = _HEAP_HeadTag;
        heapPtr->tailGuard = _HEAP_TailTag;
		heapPtr->maxSize = size;
		heapPtr->count = 0;
		heapPtr->lastUsedId = 0;
		heapPtr->cmpRtn = cmpRtn;

		for (i = 0; i <= size; i++) {
		  heapPtr->refList[i] = HEAP_NullHeapId;
		}
	  }
	}
  }

  return (heapPtr);
}

/******************************************************************
; routine:  HEAP_Free
;
; description:
;   Destroy an instance of a heap.  The destruction is a bit paranoid
;   in that it Nulls out all the pointers as it releases them.
;
; in:
;   heapPtr : HEAP_Heap -- a pointer to the heap that we want to release
;
; out:
;   none
;
; history:
;   94.10.31 / M. McAllister / Created
*******************************************************************/
void    
HEAP_Free (HEAP_Heap heapPtr)
{
  if (heapPtr != NULL) {
    /* Just to be paranoid, set the item count to 0 -- in case some
       pointer has survived. */
           
    heapPtr->count = 0;
    
    free (heapPtr->refList);
    free (heapPtr->dataList);
    free (heapPtr->idList);

    /* Null out the pointers in case somebody tries to use them elsewhere */

    heapPtr->refList  = NULL;
    heapPtr->dataList = NULL;
    heapPtr->idList   = NULL;

    free (heapPtr);
  }
}

/******************************************************************
; routine:  HEAP_Size
;
; description:
;   Provides the number of keys that are currently in a heap.
;
; in:
;   heapPtr : HEAP_Heap -- the heap whose size we want
;
; out:
;   returns : UInt16 -- the number of elements currently in the heap.
;                       calls of heap routines.
;
; history:
;   94.10.31 / M. McAllister / Created
*******************************************************************/
UInt16   
HEAP_Size(HEAP_Heap heapPtr)
{
  UInt16  size;

  if (heapPtr == HEAP_NullHeap) {
    size = 0;
  } else {
    size = heapPtr->count;
  }

  return size;
}

/******************************************************************
; routine:  HEAP_PeekTop
;
; description:
;   Retrieve the information that is at the top of the heap without
;   removing that information from the heap.
;
; in:
;   heapPtr : HEAP_Heap -- the heap whose top element we want to examine
;
; out:
;   dataPtr : Ptr * -- the data from the top of the heap
;   returns : Boolean -- True if the peek is successful
;
; history:
;   94.10.31 / M. McAllister / Created
*******************************************************************/
Boolean 
HEAP_PeekTop (HEAP_Heap heapPtr, Ptr *dataPtr)
{
  Boolean peekOkay = False;

  if ((heapPtr == NULL) || (heapPtr->count == 0)) {
    *dataPtr = NULL;
  } else {
    *dataPtr = heapPtr->dataList[_HEAP_FirstHeapElt];
    peekOkay = True;
  }

  return peekOkay;
}

/******************************************************************
; routine:  HEAP_PeekNamed
;
; description:
;   Retrieve the heap information for a particular entry in the heap.
;   The entry is identified by its "heap id" that was returned by
;   the heap add routine.
;
; in:
;   heapPtr : HEAP_Heap -- the heap into which we want to look
;   heapId : HEAP_HeapId -- the heap identifier for the part of the heap
;                       that we want to retrieve
;
; out:
;   dataPtr : Ptr * -- the heap data that is stored for the given heapId
;   returns : Boolean -- True if the retrieval was successful.
;
; history:
;   94.10.31 / M. McAllister / Created
;   94.11.01 / M. McAllister / Range check the heap Id
*******************************************************************/
Boolean 
HEAP_PeekNamed (HEAP_Heap heapPtr, HEAP_HeapId heapId, Ptr *dataPtr)
{
  UInt16  realOffset;
  Boolean peekOkay = False;

  if ((heapPtr == NULL) || (heapId == HEAP_NullHeapId) || 
      (heapId > heapPtr->maxSize) || (heapId < _HEAP_FirstHeapElt)) {
    *dataPtr = NULL;
  } else {

    /* The actual data to return must be found through indirection
       via the reference list. */

    realOffset = heapPtr->refList[heapId];
    if ((heapPtr->count == 0) || (realOffset == HEAP_NullHeapId)) {
      *dataPtr = NULL;
    } else {
      *dataPtr = heapPtr->dataList[realOffset];
      peekOkay = True;
    }
  }
  return peekOkay;
}

/******************************************************************
; routine:  SwapHeapItems
;
; description:
;  Interchange the place of two entries in a heap.
;
; in:
;   heapPtr : HEAP_Heap -- the heap in which the swap is occurring
;   first : UInt16 -- the array index in the heap of the first entry to
;                    swap
;   second : UInt16 -- the array index in the heap of the second entry to
;                     swap
;
; out:
;   none
;
; implementation:
;   The routine assumes that both "first" and "second" are within
;   the array bounds for the heap.
;
; history:
;   94.10.31 / M. McAllister / Created
*******************************************************************/
static void 
SwapHeapItems (HEAP_Heap heapPtr, UInt16 first, UInt16 second)
{
  Ptr     tempDataPtr;
  HEAP_HeapId tempId;

  if (first != second) {
    /* First, set the cross referencing in order */

    heapPtr->refList[heapPtr->idList[first]] = second;
    heapPtr->refList[heapPtr->idList[second]] = first;

    /* Next, rearrange the actual heap information */

    tempDataPtr = heapPtr->dataList[first];
    tempId = heapPtr->idList[first];
      
    heapPtr->dataList[first] = heapPtr->dataList[second];
    heapPtr->idList[first] = heapPtr->idList[second];
          
    heapPtr->dataList[second] = tempDataPtr;
    heapPtr->idList[second] = tempId;
  }
}

/******************************************************************
; routine:  ClearHeapItem
;
; description:
;   Set up a currently used heap entry as unused.
;
; in:
;   heapPtr : HEAP_Heap -- the heap in which we are moving the data
;   entry : UInt16 -- the array index in the heap that we want to clear
;
; out:
;   none
;
; history:
;   94.10.31 / M. McAllister / Created
*******************************************************************/
static void  
ClearHeapItem (HEAP_Heap heapPtr, UInt16 entry)
{
  if ((entry <= heapPtr->maxSize) && 
      (heapPtr->idList[entry] != HEAP_NullHeapId)) {

    /* Clear out the spots that we just moved. */

    heapPtr->refList[heapPtr->idList[entry]]  = HEAP_NullHeapId;
    heapPtr->dataList[entry] = NULL;
    heapPtr->idList[entry]   = HEAP_NullHeapId;
  }
}

/******************************************************************
; routine:  TrickleUp
;
; description:
;   Given a position in the heap, attempt to propagate the entry
;   up in the heap as far as possible, swapping it with its parent.
;   This is the first stage in adding a new entry to the heap.
;
; in:
;   heapPtr : HEAP_Heap -- the heap in which we are moving the data
;   trickeStart : UInt16 -- the array index in the heap that we want
;                          to propagate up the heap
;
; out:
;   returns : UInt16 -- The final array index in the heap for the
;                      entry that we were trying to propagate up.a
;
; implementation:
;   The routine assumes that "trickleStart" lies within the bounds of
;   the heap array.
;
; history:
;   94.10.31 / M. McAllister / Created
*******************************************************************/
static UInt16 
TrickleUp(HEAP_Heap heapPtr, UInt16 trickleStart)
{
  UInt16  parent, child;
  Boolean done;
  
  child = trickleStart;
  done = False;
  while ( (child > _HEAP_FirstHeapElt) && (done == False) ) {
    parent = (UInt16)(child / 2);
    if ((heapPtr->cmpRtn)(heapPtr->dataList[parent], 
        heapPtr->dataList[child]) > 0 ) {
      /*  I want the smallest element at the top of the heap
          so interchange the child and parent and then
          continue with the trickle. */
                
      SwapHeapItems (heapPtr, parent, child);
      child = parent;
    } else {
      /*  The last node has gone as high up as possible in the
          heap.  Give up the trickle. */
                
      done = True;
    }
  }

  return (child);
}

/******************************************************************
; routine:  TrickleDown
;
; description:
;   Given a position in the heap array, move the value down in the
;   heap "tree" until the property of being a heap is satisfied
;   (where the value is "larger" than both its children).  This is
;   the second stage of adding a new key to the heap.
;
; in:
;   heapPtr : HEAP_Heap -- the heap in which we are moving the data
;   startPoint : UInt16 -- the index into the heap array that we want
;                         moved down in the heap.
;
; out:
;   none
;
; implementation:
;   The routine assumes that "startPoint" is a valid index into
;   the heap's array.
;
; history:
;   94.10.31 / M. McAllister / Created
*******************************************************************/
static void 
TrickleDown(HEAP_Heap heapPtr, UInt16 startPoint)
{
  UInt16  parent, child;
  Boolean done;

  /* We want to push the element at "startPoint" down as far
     in the heap as we can; continue until we either cannot
     go any deeper in the heap or until both children of the
     current position cannot be swapped with the current position. */

  parent = startPoint;
  done = False;
  while ( (parent <= heapPtr->count) && (done == False) ) {
    child = parent * 2;
    if (child > heapPtr->count) {
      done = True;
    } else {
      if ((child + 1 <= heapPtr->count) &&
          ((heapPtr->cmpRtn)(heapPtr->dataList[child], 
              heapPtr->dataList[child+1]) > 0 )) {
        child += 1;
      }
          
      /*  Now, child is pointing to the smaller of the two children
          of parent. */
      
      if ((heapPtr->cmpRtn)(heapPtr->dataList[parent], 
              heapPtr->dataList[child]) < 0 ) {
        done = True;
    } else {
        /*  The child is smaller so move him up and continue
            the restoration of the heap. */
              
        SwapHeapItems (heapPtr, parent, child);
        parent = child;
      }
    }
  } 
}

/******************************************************************
; routine:  HEAP_Add
;
; description:
;   Add data into the heap.  The routine will return False if the
;   data could not be added.  Reasons for failure are:
;     invalid heap was supplied
;     no more room left in the heap
;
; in:
;   heapPtr : HEAP_Heap -- the heap to which we want to add the element
;   data : Ptr -- the data to add to the heap
;
; out:
;   heapId : HEAP_HeapId * -- an idenfication number for the added data.
;                         The id is only unique to within the heap itself.
;   returns : Boolean -- True if the addition was successful.
;
; history:
;   94.10.31 / M. McAllister / Created
;   94.11.01 / M. McAllister / Allow heap count to reach maxSize on an add
*******************************************************************/
Boolean 
HEAP_Add (HEAP_Heap heapPtr, Ptr data, HEAP_HeapId *heapId)
{
  UInt16  upSearch;
  Boolean addOkay = False;

  if (heapPtr == NULL)  {
    /* I wasn't given a heap to add to. */

    *heapId = HEAP_NullHeapId;
  } else {  
    if (heapPtr->count + 1 > heapPtr->maxSize) {
      /* Too much stuff in the heap already */

      *heapId = HEAP_NullHeapId;
    } else {

      /* Find myself an available heap id with a linear search of 
         the reference list for now.  One must exist since the heap
         count claims that there is room left in the heap. */
      
      *heapId = (heapPtr->lastUsedId % heapPtr->maxSize) + 1;
      while (heapPtr->refList[*heapId] != HEAP_NullHeapId) {
        *heapId += 1;
      }

      /* Claim the spot in the heap. */

      heapPtr->lastUsedId = *heapId;
      heapPtr->count += 1;

      /* Put the "add" data into the heap. */

      heapPtr->dataList[heapPtr->count] = data;
      heapPtr->idList[heapPtr->count] = *heapId;
      heapPtr->refList[*heapId] = heapPtr->count;
      
      /*  Move the last node up as high in the heap as possible and
          then re-make the tree into a heap. */
  
      upSearch = TrickleUp(heapPtr, heapPtr->count);
      TrickleDown(heapPtr, upSearch);
      addOkay = True;
    }
  }
  return addOkay;
}

/******************************************************************
; routine:  HEAP_PopTop
;
; description:
;   Remove the topmost element of the heap.
;   The routine may fail if
;     an invalid heap was supplied
;     the heap is empty
;
; in:
;   heapPtr : HEAP_Heap -- the heap whose top element we want to remove
;
; out:
;   dataPtr : Ptr * -- the data stored at the top of the heap
;   returns : Boolean -- True if the removal was successful.
;
; history:
;   94.10.31 / M. McAllister / Created
*******************************************************************/
Boolean 
HEAP_PopTop (HEAP_Heap heapPtr, Ptr *dataPtr)
{
  Boolean  popOkay = False;

  if ((heapPtr == NULL) || (heapPtr->count <= 0)) {
    *dataPtr = NULL;
  } else {
    /*  First, capture the data at the start of the heap */
    
    *dataPtr = heapPtr->dataList[_HEAP_FirstHeapElt];
    
    /*  Next, move the last element to the top of the heap and
        re-create the heap property. */
        
    SwapHeapItems (heapPtr, _HEAP_FirstHeapElt, heapPtr->count);

    /* Clear out the spots that we just moved. */

    ClearHeapItem (heapPtr, heapPtr->count);
    heapPtr->count -= 1;

    TrickleDown(heapPtr, _HEAP_FirstHeapElt);

    popOkay = True;
  }

  return popOkay;
}

/******************************************************************
; routine:  HEAP_PopNamed
;
; description:
;   Remove a specific entry from the heap, as identified by the heap id.
;   The routine may fail if
;     an invalid heap was supplied
;     the heap id supplied is not valid (an old id or the heap is empty)
;
; in:
;   heapPtr : HEAP_Heap -- the heap whose top element we want to remove
;   heapId : HEAP_HeapId -- the reference id for the heap entry that must
;                       be deleted.
;
; out:
;   dataPtr : Ptr * -- the data stored at the top of the heap
;   returns : Boolean -- True if the removal was successful.
;
;
; history:
;   94.10.31 / M. McAllister / Created
;   94.11.01 / M. McAllister / Range check the heap Id
*******************************************************************/
Boolean 
HEAP_PopNamed (HEAP_Heap heapPtr, HEAP_HeapId heapId, Ptr *dataPtr)
{
  UInt16  realOffset;
  UInt16  upSearch;
  Boolean removeOkay = False;

  if ((heapPtr == NULL) || (heapId > heapPtr->maxSize) || 
      (heapId < _HEAP_FirstHeapElt)) {
    *dataPtr = NULL;
  } else {
    realOffset = heapPtr->refList[heapId];
    if ((heapPtr->count == 0) || (realOffset == HEAP_NullHeapId)) {
      *dataPtr = NULL;
    } else {
      /* I actually have something to remove.  Remove it by
          1. exchange it with the last element in the tree
          2. trickle the new item up and then down the tree.
      */

      *dataPtr = heapPtr->dataList[realOffset];

      SwapHeapItems (heapPtr, realOffset, heapPtr->count);

      /* Clear out the spots that we just moved. */

      ClearHeapItem (heapPtr, heapPtr->count);
      heapPtr->count -= 1;

      /* Only need to rebalance if we didn't remove the last entry. */

      if (realOffset <= heapPtr->count) {
        upSearch = TrickleUp(heapPtr, realOffset);
        TrickleDown(heapPtr, upSearch);
      }

      removeOkay = True;
    }
  }

  return removeOkay;
}

/******************************************************************
; routine:  HEAP_Print
;
; description:
;   Display a representation of the heap.
;
; in:
;   heapPtr : HEAP_Heap -- the heap to display
;
; out:
;   none
;
; implementation:
;   The routine is currently a hack; don't rely on it being here in the
;   future.
;
; history:
;   94.10.31 / M. McAllister / Created
*******************************************************************/
void    
HEAP_Print (HEAP_Heap heapPtr)
{
  UInt16 i;

  if (heapPtr == NULL) {
    printf ("Heap does not exist\n");
  } else {
    if (heapPtr->count == 0) {
      printf ("Heap is empty\n");
    } else {
      for (i = 1; i <= heapPtr->count; i++) {
        printf ("%x\n", heapPtr->dataList[i]);
      }
    }
  }
}

/******************************************************************
; routine:  HEAP_Audit
;
; description:
;   Performs some consistency checking over the given heap.
;   Returns True if all the tests passed and the heap looks sane.
;
; in:
;   heapPtr : HEAP_Heap -- the heap to audit
;
; out:
;   returns : Boolean -- True if the heap looks sane
;
; implementation:
;   The audit consists of checking the following characteristics:
;     The memory guards are intact
;     The "heap" property is intact -- parents are bigger than their children
;     The number of entries in the heap matches the number of unused
;       heap ids.
;     For valid heap ids, referencing through the refList to the idList
;       should yield the same index number;
;
; history:
;   94.10.31 / M. McAllister / Created
;   94.11.01 / M. McAllister / Consider the Null heap as "sane"
*******************************************************************/
Boolean    
HEAP_Audit (HEAP_Heap heapPtr)
{
  Boolean   sane = False;
  UInt16    outOfOrder;
  UInt16    i;
  UInt16    usedRefs;
  UInt16    crossRefMismatch;

  if (heapPtr == NULL) {
    /* No heap is a sane heap, despite its degeneracy. */
    sane = True;
  } else {
    /* Check the memory guards */

    if ((heapPtr->headGuard != _HEAP_HeadTag) || 
        (heapPtr->tailGuard != _HEAP_TailTag)) {
      sane = False;
    } else {

      /* Check the "heap" property; count how many times entries
         are found to be out of order. */

      outOfOrder = 0;
      for (i = _HEAP_FirstHeapElt; i <= heapPtr->count; i++) {
        if (((heapPtr->count >= 2*i) && ((heapPtr->cmpRtn)
                  (heapPtr->dataList[i], heapPtr->dataList[2*i]) > 0)) ||
            ((heapPtr->count >= (2*i+1)) && ((heapPtr->cmpRtn)
                  (heapPtr->dataList[i], heapPtr->dataList[2*i + 1]) > 0))) {
          outOfOrder ++;
        }
      }

      if (outOfOrder != 0) {
        /* At least two elements aren't in order.  We don't have a heap.  */

        sane = False;
      } else {

        /* Make sure that the heap entry count matches the contents
           of the heap itself. */

        usedRefs = 0;
        crossRefMismatch = 0;
        for (i = 0; i <= heapPtr->maxSize; i++) {
          if (heapPtr->refList[i] != HEAP_NullHeapId) {
            usedRefs++;
            if (heapPtr->idList[heapPtr->refList[i]] != i) {
              crossRefMismatch++;
            }
          }
        }

        if ((heapPtr->count != usedRefs) ||
            (crossRefMismatch != 0)) {
          /* The unused references does not match the count in the head
             or the cross referencing is messed up. */

          sane = False;
        } else {
          /* The heap is sane, as far as I can tell. */

          sane = True;
        }
      }
    }
  }

  return sane;
}

